//: [Previous](@previous)

import Foundation

//dp dp[n] = dp[n-1]+dp[n-2]  dp[n-1]最多步数+1  dp[n-2]最多步数+2
func numWays(_ n: Int) -> Int {
    if n < 2 {
        return 1
    }
    var list = Array(repeating: 0, count: n+1)
    list[0] = 1
    list[1] = 1
    
    for index in 2...n {
        list[index] = list[index-1]+list[index-2]
    }
    return list[n]
}
